#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        vector<vector<bool>> visted(board.size(), vector<bool>(board[0].size(), false));
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (dfs(board, visted, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
private:
    bool dfs(vector<vector<char>>& board,vector<vector<bool>>&visted, string word, int i, int j, int index) {
        if (index == word.length()) { return true; }
        if(i<0||i>=board.size()||j<0||j>=board[0].size()||
            visted[i][j] || board[i][j] != word[index]) {
            return false;
        }
        visted[i][j] = true;
        bool found = dfs(board, visted, word, i + 1, j, index+1) ||
            dfs(board, visted, word, i - 1, j, index+1) ||
            dfs(board, visted, word, i, j + 1, index+1) ||
            dfs(board, visted, word, i, j - 1, index+1);
            visted[i][j] = false;
            return found;
    }
};